\documentclass[geye,green,pad,cn]{elegantnote}

\title{\bfseries 格理论\\{\small(笔记)}}

\author{方徽星}
\date{\small\itshape 版本：1.00 \\ 更新时间：\today}

\usepackage{listings} 
\lstset{language=[LaTeX]{TeX},basicstyle=\footnotesize\ttfamily}


\usepackage{tikz}
\begin{document}
{\color{ecolor}{\maketitle}}
% logo




\section{基础概念}

\begin{definition}[Irreflexive transitive closure-反自反传递闭包]

给定集合X上的任一关系$R$，定义$R$的反自反传递闭包$R^+$如下：

任意$x,y \in X:(x,y) \in R^+$ 当且仅当存在序列$x_0,x_1,\cdots,x_j$,使得
$\forall i:0 \leq i<j:(x_i,x_{i+1} )\in R$成立，
其中$j\geq 1$且$x_0=x,x_j=y$.



\end{definition}
也就是说，$(x,y)\in R^+$ 当且仅当
在关系$R$的图中存在一条从$x$到$y$的非空路径.


\begin{definition}[Reflexive transitive closure-自反传递闭包]

给定集合$X$上一个关系$R$，定义自反传递闭包$R^*$：
$R^*=R^+ \cup \{(x,x)  \mid x \in X \}.$
也就是说，$(x,y)\in R^*$当且仅当在关系$R$的图中，从$x$出发有一条路径到达$y$，该路径由$0$条或多条边构成.

\end{definition}


\begin{definition}[Reflexive partial order-自反偏序]

集合$X$上的一个关系$R$是一个自反偏序（也称为nonstrict partial order）需满足：
\vspace{-3mm}
\begin{enumerate}
	\item 自反性-$reflexive$，
	\item 反对称性-$antisymmetric$,以及
	\item 	传递性-$transitive$.
\end{enumerate}
	
\end{definition}

\begin{example}[自反偏序]
定义在自然数集合上的整除关系即是自反偏序的一个典型实例.
	\vspace{-3mm}\begin{enumerate}
		\item 自反性：$2$可以整除$2$自己，
		\item 反对称性：$2$可以整除$4$，但$4$不能整除$2$，
		\item 传递性：$2$能整除$4$，$4$能整除$8$，$2$能整除$8$.
	\end{enumerate}
\end{example}

\begin{note}[符号约定poset]
	若$R$是一个自反偏序，
	常用$x \leq_R y$(或$x \leq y$)
	表示$(x,y)\in R$.		
	常用$\bf{poset}$作为reflexive partially ordered set的简称，以二元组$(X,\leq)$表示$\bf{poset}$（偏序集）.	
\end{note}	


\begin{definition}[irreflexive partial order-反自反偏序]	
集合$X$上一个关系$R$是一个反自反偏序（irreflexive partial order or strict partial order）需满足两个性质：
	反自反性和传递性.
	
\end{definition}

\begin{example}[反自反偏序]
定义在自然数集合上的小于关系即为反自反偏序的一个典型实例.
\end{example}

\begin{note}[符号约定:反自反偏序]
若$R$是反自反偏序，常用符号$x <_R y$(或$x < y$)表示$(x,y) \in R$.
常用$\bf{irreflexive~poset}$作为irreflexive partially ordered set的简称，以二元组$(X,<)$表示反自反偏序.
\end{note}


\begin{definition}[total order-全序]
若$R$是一个偏序，且任取两个互异元素$x,y \in X$，要么我们有$(x,y) \in R$，要么有$(y,x) \in R$ (有且仅有$1$个成立)，则$R$是全序.
\end{definition}

\begin{example}[全序]
整数集合上的自然序是一种全序.
整除关系仅仅是一种偏序，而不是全序.（$2$和$5$，$2$不整除$5$，$5$也无法整除$2$）.
\end{example}

\begin{definition}[comparable and incomparable-可比与不可比]
令$x,y\in X$且$x \neq y$. 如果$x<y$或$y<x$，则$x$和$y$是可比的（Comparable）.如果$x<y$和$y<x$均不成立，则$x$和$y$是不可比的（Incomparable）.
\end{definition}


\begin{definition}[chain-链]
给定一个偏序集$(Y,\leq)$，若$Y$中任意两个不同元素都是可比的，则该偏序集是一条链$(chain)$.
\end{definition}


\begin{definition}[antichain-反链]
给定一个偏序集$(Y, \leq)$，若Y中不存在两个可比的不同元素，则该偏序集是一条反链(antichain).
\end{definition}

\begin{example}[longest chain-最长链]
若我们称链$C$是偏序集$(X,\leq)$的一条最长链，则$C$需满足约束：偏序集$(X,\leq)$不存在其他链比$C$含有更多的元素.	
\end{example}

\begin{note}[最长反链]
最长反链（longest antichain）也可参照上述方式进行定义.
\end{note}

\begin{definition}[height-偏序集的高度]
偏序集的一条最长链中含有的元素数量称为该偏序集的高度.	
\end{definition}

\begin{definition}[width-偏序集的宽度]	
偏序集的一条最长反链中含有的元素数量称为该偏序集的宽度.
\end{definition}

\begin{definition}[interval-区间]
偏序集$(X,\leq)$的一个区间$[x,y]$定义为集合$\{z \mid x\leq z \leq y\}$. 其他区间$(x,y)$,$[x,y)$和$(x,y]$可以类似方式来定义.
\end{definition}

\begin{definition}[locally finite-局部有限]
如果一个偏序集的所有区间都是有限的，则该偏序集是局部有限的.
\end{definition}
	
	
\begin{definition}[well founded-良基的]
一个偏序集是良基的当且仅当该偏序集中不含有无限递减链(infinite decreasing chain).
\end{definition}	


\begin{example}
	考虑普通的$\leq$（小于等于）关系时，自然数集是良基的，但整数集不是良基的.
\end{example}	

\begin{definition}[extends-扩展]
	给定偏序集$Q=(X,\leq_Q)$和偏序集$P=(X,\leq_P)$，如果
$\forall x,y\in X: x \leq_P y \implies x \leq_Q y$.
	则称$Q$扩展 $P$.如果$Q$还是一个全序，则称$Q$是$P$的一个线性扩展.
	
\end{definition}	

\begin{example}
给定$X=\{p,q,r,s\}$，$\leq_P=\{(p,q),(p,s),(q,r),(p,r)\}$，若
$$\leq_Q=\{(p,q),(p,s),(q,r),(p,r),(q,s),(r,s)\},$$
则表明$Q$是$P$的一个线性扩展.
	
	
	$\bf{Meet~and~Join}$
	
给定集合$X$，在$X$的子集上可以定义两种运算，分别是$meet$和$join$.

$meet$运算也称infimum（或inf），中文含义是下确界.

$join$运算也称supremum（或sup），含义是上确界.


\begin{figure}[h]
	\begin{center}
\begin{tikzpicture}
\draw 
(1,3)--(1,1)--(4,1)--(4,3);

\draw (2.5,-0.5) ellipse (1 and 1.47);

\draw (1,-4)--(1,-2)--(4,-2)--(4,-4);

\node at (2.5, 1.2) {join};
\node at (2.5, -2.2) {meet};
\node at (2.5, 1.6) {上确界};
\node at (2.5, -2.6) {下确界};
\node at (2.5, -3) {inf};
\node at (2.5, 2) {sup};
\end{tikzpicture}
\caption{join和meet}
\end{center}
\end{figure}		

\end{example}	


\begin{definition}[inf-下确界]
令$Y \subset X$，其中$(X,\leq)$是一个偏序集.
任意$m \in X$，称$m=\inf{Y}$
($m$是$Y$的下确界，$m$未必属于$Y$)当且仅当：
\begin{enumerate}
	\item 
	$\forall y\in Y:m\leq y$ (意思表明m是Y的一个下界)且
	
	\item $\forall m' \in X:(\forall y\in Y: m'\leq y)\implies m'\leq m$.(意思是$Y$的所有下界都小于等于$m$)
\end{enumerate}
因此，$m$是$Y$的最大下界（greatest lower bound，缩写为glb）.


	
\end{definition}
\begin{note}[符号约定-glb-$\sqcap$]
	集合$\{a,b\}$的glb常记为$a \sqcap b$.
\end{note}


\begin{example}[glb]
考虑偏序集（自然数集，整除），$glb$运算表示找到子集的最大公约数.
\end{example}

\begin{definition}[sup-上确界]
任意$s\in X$，称$s=\sup{⁡}$
($s$是$Y$的上确界，$s$未必属于$Y$）当且仅当：
\begin{enumerate}
	\item 	$\forall y\in Y:y \leq s$ (意思表明$s$是$Y$的一个上界)且
	\item $\forall s'\in X:(\forall y\in Y:y\leq s' ) \implies s\leq s'$.(意思是$s$小于等于$Y$的所有上界)	
\end{enumerate}
	因此，$s$是$Y$的最小上界（least upper bound，缩写为lub）.
\end{definition}

\begin{note}[符号约定-lub-$\sqcup$]
	集合$\{a,b\}$的$lub$常记为$a \sqcup b$.
\end{note}		

\begin{example}[lub]
	考虑偏序集（自然数集，整除），$lub$运算表示找到子集的最小公倍数.
\end{example}	


\begin{lemma}[连接-Connecting]
	对于一个偏序集中的所有元素x和y，有如下结论:
	\begin{enumerate}
		\item 	$x\leq y \equiv (x \sqcup y)=y$, 
		\item 	$x \leq y \equiv (x \sqcap y)=x$.
	\end{enumerate}

\end{lemma}	
\begin{proof}
首先证明$x\leq y \equiv (x \sqcup y)=y$, 
分两步走：
\begin{enumerate}
	\item $x \leq y  \implies (x \sqcup y)=y:$ 由$x \leq y$可知$y$是$\{x,y\}$的1个上界，
	任取$y'$为$\{x,y\}$的另1个上界，则根据上界定义可知$x\leq y'$且$y\leq y'$，由$y\leq y'$可知$y$小于等于$\{x,y\}$的所有上界，因此$y$必为最小上界，$(x \sqcup y)=y$.
	
	\item $(x \sqcup y)=y \implies x \leq y:$由$(x \sqcup y)=y$可知$y$是$\{x, y\}$的最小上界，所以有$x\leq y$ 和$y\leq y$.
\end{enumerate}


综合以上两步，$x \leq y \equiv (x \sqcup y)=y$ 得证. 通过构造类似证明(对偶)，$x \leq y \equiv (x \sqcap y)=x$也可证.
	
\end{proof}


\begin{definition}[lattice-格]
一个偏序集$(X,\leq)$称为一个格当且仅当
$\forall x,y\in X:x \sqcup y$和$x \sqcap y$均存在.
\end{definition}


\begin{figure}[h]
	\begin{center}
		\begin{minipage}[b]{0.3\textwidth}
			\centering
				\begin{tikzpicture}[every node/.style={draw, circle,fill=blue!30,node distance=1.5cm}]
				\node (a) at (1,1) {$a$};
				\node[above left of=a] (b) {$b$};
				\draw (a)--(b);
				\node[above right of=a] (c) {$c$};
				\draw (a)--(c);
				\node[above of=b] (d) {$d$};
				\draw (b)--(d);
				\node[above right of=d] (e) {$e$};
				\draw (d)--(e);						\draw (c)--(e);						
			\end{tikzpicture}
		\captionof{figure}{偏序集-1}
		\label{fig:poset-1}
		\end{minipage}
	\begin{minipage}[b]{0.2\textwidth}
		\centering
		\begin{tikzpicture}[every node/.style={draw, circle,fill=blue!30,node distance=3cm}]
			\node (a) at (1,1) {$a$};
			\node[above of=a] (b) {$b$};
			\draw (a)--(b);							
		\end{tikzpicture}
		\captionof{figure}{偏序集-2}
		\label{fig:poset-2}
	\end{minipage}
\begin{minipage}[b]{0.3\textwidth}
	\centering
	\begin{tikzpicture}[every node/.style={draw, circle,fill=blue!30,node distance=1.5cm}]
		\node (a) at (1,1) {$a$};
		\node[above left of=a] (b) {$b$};
		\draw (a)--(b);
		\node[above right of=a] (c) {$c$};
		\draw (a)--(c);
		\node[above of=b] (d) {$d$};
		\draw (b)--(d);
		\node[above of=c] (e) {$e$};
		\draw (c)--(e);		
		\node[above right of=d] (f) {$f$}; 		
		\draw (d)--(f);
		\draw (e)--(f);
		\draw (b)--(e);
		\draw (c)--(d);		
	\end{tikzpicture}
	\captionof{figure}{偏序集-3}
	\label{fig:poset-3}
\end{minipage}
    \end{center}
\end{figure}

\begin{example}[格]
	图\ref{fig:poset-1}和\ref{fig:poset-2}均为格.
	而图\ref{fig:poset-3}不是格.
	
	我们来分析看看图\ref{fig:poset-3}偏序集：集合$\{b, c\}$有三个上界，分别是d、e和f，用集合$U=\{d,e,f\}$表示. 我们能否在U中找到一个最小元？
	若取d为最小元：需要同时满足
	\begin{enumerate}
		\item 	$d\leq d$,
		\item   $d\leq e$,
	    \item   $d\leq f$，
	\end{enumerate}

	我们知道(2)是无法满足的，因为d和e是不可比的;
	同理，若取e为最小元：则因为d和e是不可比的，无法使得
	$e\leq d$;
	若取f为最小元：则需要同时满足
	\begin{enumerate}
		\item $f\leq d$,
		\item $f\leq e$,
		\item $f\leq f$，
	\end{enumerate}

	我们知道(1)和(2)是不可满足的，因为我们已经有	
	$d\leq $和$e\leq f$，根据反对称性，无法使得(1)和(2)满足.
	
	通过如此分析，可知所有可能的情况下我们均无法在$U$中找出最小元，从而，不存在$b \sqcup c$.
	
\end{example}



{\bfseries{半格}}

$\bf{sup~semilattice}$: 如果$\forall x,y \in X: x \sqcup y$存在，则$(X, \leq)$是sup~semilattice.

$\bf{inf~semilattice}$: 如果$\forall x,y \in X: x \sqcap y$存在，则$(X, \leq)$是inf~semilattice.

\end{document}



